class Solution(object):
    def longestIncreasingPath(self, matrix):
        """

        :param matrix:
        :return:
        """
        h = len(matrix)
        if h == 0:
            return 0
        w = len(matrix[0])
        def dfs(x, y):
            for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w and matrix[nx][ny] > matrix[x][y]:
                    if not dp[nx][ny]:
                        dp[nx][ny] = dfs(nx, ny)
                    dp[x][y] = max(dp[x][y], dp[nx][ny] + 1)
            dp[x][y] = max(dp[x][y], 1)#　基本条件,当四个位移均不满足条件时将此位置上的dp设为1
            return dp[x][y]
        dp = [[0] * w for _ in range(h)]
        for x in range(h):
            for y in range(w):
                if not dp[x][y]:
                    dp[x][y] = dfs(x, y)
        return max([max(x) for x in dp])

test = Solution()
print(test.longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]]))